'''
https://leetcode.cn/problems/evaluate-division/description/?envType=study-plan-v2&envId=top-interview-150
'''
from collections import defaultdict, deque
from typing import List


class UF:
    def __init__(self, n):
        # x: 某个节点
        # v[x]: 假设这个节点的实际值
        # f[x]: 这个节点的父亲节点，在并查集中
        # 设 w[x]=v[x]/v[fx], 他与father的比值
        # 若f为x,y的共同祖先且 v[x]/v[f]=a,v[y]/v[f]=b，则 v[x]/v[y]=a/b。
        #           也就是v[x]/v[y] = w[x]/w[y]
        # find father 时，如果修改f[x]时，如何设置新的w[x]    ==============
        #     在find father，直连father时
        #       w[x] = v[x] / v[newfather]
        #            = (v[x]/v[oldfather]) * (v[oldfather] / v[newfather])
        #            = w[x] * w[oldfather]
        # 合并的时候计算w[fx]===============================
        # w[x] = v[x] / v[fx]       v[x] = v[fx] * w[x]
        # w[y] = v[y] / v[fy]       v[y] = v[fy] * w[y]
        # and   v[x]/v[y] = c       v[fx]*w[x]/v[fy]/w[y] = c
        #       w[fx]*w[x]/w[y] = c
        #       w[fx] = c*w[y]/w[x]
        self.father = [i for i in range(n)]
        self.weight = [1] * n
    def find(self, i):
        if self.father[i] != i:
            oldfather = self.father[i]
            self.father[i] = self.find(oldfather)
            self.weight[i] = self.weight[i] * self.weight[oldfather]
        return self.father[i]
    def is_same_set(self, x, y):
        return self.find(x) == self.find(y)
    def union(self, x, y, ratio):
        fx, fy = self.find(x), self.find(y)
        self.father[fx] = fy
        self.weight[fx] = self.weight[y] * ratio / self.weight[x]


class Solution:
    # 并查集
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        id = {}
        n = 0
        for u, v in equations:
            if u not in id:
                id[u] = n
                n += 1
            if v not in id:
                id[v] = n
                n += 1

        uf = UF(n)
        for (u, v), w in zip(equations, values):
            uf.union(id[u], id[v], w)
        res = []
        for x,y in queries:
            if x not in id or y not in id or not uf.is_same_set(id[x], id[y]):
                res.append(-1.0)
            else:
                res.append(uf.weight[id[x]] / uf.weight[id[y]])
        return res

    # floyd, 预处理所有节点之间的距离(倍数)
    def calcEquation2(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        id = {}
        n = 0
        graph = defaultdict(list)
        for i, eq in enumerate(equations):
            u, v, w = eq[0], eq[1], values[i]
            if u not in id:
                id[u] = n
                n += 1
            if v not in id:
                id[v] = n
                n += 1
            graph[id[u]].append((id[v], w))
            graph[id[v]].append((id[u], 1/w))

        distances = [[float('inf')] * n for _ in range(n)]
        for u in range(n):
            distances[u][u] = 1
            for v, w in graph[u]:
                distances[u][v] = w
        for m in range(n):
            for u in range(n):
                for v in range(n):
                    if distances[u][m] and distances[m][v]\
                            and distances[u][m] * distances[m][v] < distances[u][v]:
                        distances[u][v] = distances[u][m] * distances[m][v]
        res = []
        for u, v in queries:
            if u not in id or v not in id:
                res.append(-1.0)
                continue
            u, v = id[u], id[v]
            if distances[u][v] != float('inf'):
                res.append(distances[u][v])
            else:
                res.append(-1.0)
        return res

eqs = [["a","b"],["b","c"]]
values = [2.0,3.0]
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
print(Solution().calcEquation(eqs, values, queries))